/**
 * Hash桶
 * 
 * @author shuyuan.dai 2021-03-25
 */
class HashBucket {
    constructor(items, initCapacity = 1) {
        this.tableSize = this.tableSizeFor(initCapacity);
        this.limit = 1 / this.tableSize;
        this.buckets = new Array(this.tableSize);
        this.colds = new Map();
        this.unHits = 0;

        let split = Math.floor(items.length / this.tableSize);
        for(let i=0; i < this.tableSize; ++i) {
            this.buckets[i] = [];
            for(let j=0; j < split && items.length > 0; ++j) {
                this.buckets[i].push(items.pop());
            }
            this.colds.set(i, 0);
        }
    }

    getItem(code, cycle = true) {
        let index = this.calIndex(code);
        if(this.buckets[index].length > 0) {
            if(Math.random() < this.limit) {
                if(this.colds.has(index)) {
                    this.colds.set(index, this.colds.get(index) + 1);
                }
            }
            return this.buckets[index].shift();
        }

        this.unHits++;
        if(this.colds.has(index)) {
            this.colds.delete(index);
        }

        if(cycle) {
            for(let offset = 1, nextIndex; (nextIndex = this.calIndex(code, offset)) != index; ++offset) {
                if(this.buckets[nextIndex].length > 0) {
                    return this.buckets[nextIndex].shift();
                }
            }
        } else if(this.colds.size > 0) {
            let min = Infinity, nextIndex = -1;
            this.colds.forEach((v, k) => {
                if(min > v) {
                    min = v;
                    nextIndex = k;
                }
            });
            if(nextIndex >= 0) {
                this.buckets[nextIndex].shift();
            }
        }

        return null;
    }

    calIndex(code, offset = 0) {
        code += offset;
        return ((code & 0xFFFF) ^ (code >>> 16)) & (this.tableSize - 1);
    }

    tableSizeFor(cap) {
        let n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return Math.max(n + 1, 1);
    }
}

exports.HashBucket = HashBucket;